package com.murphy.algorithm.sort;

import com.alibaba.fastjson.JSON;

/**
 *插入排序
 * 将数组分为两段，前半段是已经有序的，，后半段无需
 * 每次循环只需要跟前半段比较，找到比自己小的，插入到这个数后面即可
 * 如果前一个数比当前数还大，就将数往后移，跟再前一个做比较，直到前一个数比当前值小，就将当前数插入这个数后面
 * 时间复杂度：O(n*n)
 * 空间复杂度：O(1)
 * @author dongsufeng
 * @date 2020/9/10 15:48
 * @version 1.0
 */
public class InsertionSort {

	public void sort(int [] items){
		//外层循环从1开始，0无需往前对比
		for (int i = 1 ;i < items.length ; i++){
			//将要对比的基准值放入临时字段
			int temp = items[i];
			//内层循环从外层循环开始值往前循环和基准值对比
			int j = i-1;
			for (;j>=0;j--){
				//往前循环对比，如果比基准值大，则后移动（基准值的位置是空的）
				if (items[j]>temp){
					items[j+1] = items[j];
				}else {
					break;
				}
			}
			//将基准值插入到空出的位置
			items[j+1] = temp;
		}
	}

	public static void main(String[] args) {
		InsertionSort sort=new InsertionSort();
				int [] items={6,3,7,2,4,5,1,9,8};
//				int [] items={9,8,7,6,5,4,3,2,1};
//		int [] items={1,2,3,4,5,6,7,8,9};
		sort.sort(items);
		System.out.println(JSON.toJSONString(items));
	}
}
